Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Number of Islands

Problem Statement

Given a 2D array (i.e., a matrix) containing only 1s (land) and 0s (water), count the number of islands in it.

An island is a connected set of 1s (land) and is surrounded by either an edge or 0s (water). Each cell is considered connected to other cells horizontally or vertically (not diagonally).

Example 1

Input: matrix =

Image

Output: 3
Explanation: The matrix has three islands. See the highlighted cells below.

Image

Example 2

Input: matrix =

Image

Output: 1
Explanation: The matrix has only one island. See the highlighted cells below.

Image

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.

Solution

We can traverse the matrix linearly to find islands.

Whenever we find a cell with the value '1' (i.e., land), we have found an island. Using that cell as the root node, we will perform a Depth First Search (DFS) or Breadth First Search (BFS) to find all of its connected land cells. During our DFS or BFS traversal, we will find and mark all the horizontally and vertically connected land cells. 

We need to have a mechanism to mark each land cell to ensure that each land cell is visited only once. To mark a cell visited, we have two options:

  1. We can update the given input matrix. Whenever we see a '1', we will make it '0'.
  2. A separate boolean matrix can be used to record whether or not each cell has been visited. 

Following is the DFS or BFS traversal of the example-2 mentioned above:

Image

By following the above algorithm, every time DFS or BFS is triggered, we are sure that we have found an island. We will keep a running count to calculate the total number of islands.

Below, we will see three solutions based on:

  1. DFS
  2. BFS
  3. BFS with visited matrix

Code  (DFS)

Here is what our DFS algorithm will look like. We will update the input matrix to mark cells visited.

Java
Saved to Cloud

. . . .

Time Complexity
Time complexity of the above algorithm will be , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix. This is due to the fact that we have to traverse the whole matrix to find the islands.

Space Complexity
DFS recursion stack can go deep when the whole matrix is filled with '1's. Hence, the space complexity will be , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix.

Code  (BFS)

Here is what our BFS algorithm will look like. We will update the input matrix to mark cells visited.

Java

. . . .

Time Complexity
Time complexity of the above algorithm will be , where ‘M’ is the number of rows and 'N' is the number of columns.

Space Complexity
Space complexity of the above algorithm will be . In the worst case, when the matrix is completely filled with land cells, the size of the queue can grow up to .

Code  (BFS with visited matrix)

Here is what our BFS algorithm will look like. We will keep a separate boolean matrix to record whether or not each cell has been visited.

Java

. . . .

Time Complexity
Time complexity of the above algorithm will be , where ‘M’ is the number of rows and 'N' is the number of columns.

Space Complexity
Because of the visited array and max size of the queue, the space complexity will be , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix.

Number of Islands (medium)
Clone Graph (medium)
Mark as Completed

On this page

Problem Statement

Solution

Code  (DFS)

Code  (BFS)

Code  (BFS with visited matrix)